The growing network of packet based routers and bridges used in the Internet and other packet networks in addition to the increased network speeds of routing packets, such as 10 Gigabits per second, as specified in Optical Carrier standard document OC-192, require more efficient handling of the task of looking up forwarding information stored in a FIB table. These FIB tables are found in routers and bridges, for example, and are used to determine how to route an outgoing packet.
Looking up the outgoing port number upon receipt of an incoming packet in a FIB table is typically complex because variable length prefix keys are utilized to determine if an entry in the FIB table matches a unique key extracted from the incoming packet. Considering that the incoming packet contains an IP destination address which has 32 bits, typical variable length prefixes have lengths ranging from 1 to 32 bits. When a prefix has a length less than 32 bits, a 32 bit word is still typically stored in the FIB table and only the prefix bits are matched against the IP destination address and the unused bits are considered operationally as “don't cares”, meaning those bits are not compared to the incoming packet's destination address.
Adding to the complexity of looking up data in a FIB table, shorter length prefixes may be subsets of longer length prefixes which would typically result in multiple matches. To resolve multiple matches, the Internet protocol specifies that the longest length mask which matches the incoming key's destination address should be chosen.
Considering the expanding Internet network and the speed at which data travels through the network, the FIB table lookup problem often requires the capability for achieving a sustained packet forwarding rate of at least 25 million packets per second (MPPS), while maintaining an update rate of at least 2000–3000 updates per second. Any solution further requires handling burst FIB table update rates that can be up to 10 times higher than steady state rates. Also the FIB table should be available for lookup at all times in order to minimize the packet drop rate.
There have been many solutions to the FIB table lookup problem. Typical software approaches usually employ radix tree techniques. As a result, software approaches are relatively slow and do not scale well with the increasing size of the Internet and the speed at which data travels through the Internet. To achieve the desired speeds, a typical hardware approach employs ternary content addressable memory (TCAM) device which is based on a special circuit design. A typical TCAM device requires approximately 16 transistors to store one bit of information. Since the current manufacturing technology and state of the art circuit design limits TCAM chips to 18 megabits per chip, assuming 128 k entries with a table entry size of 144 bits, a single TCAM chip may consume up to 300 million transistors, thus pushing the limits of the state of the art silicon manufacturing process.
To address the specific FIB table lookup problem of multiple matches of differing length prefixes, one TCAM approach requires shorter length prefixes that are subsets of longer length prefixes to be stored physically together in a group and in descending order from longest length prefix to shorter length prefix. The longer length prefix is returned because upon matching an incoming packet's key, the approach finds the prefix group and steps through comparing each prefix, starting with the longest prefix and progressing through to the shortest prefix until a first match is found. This typical sequential progression requires that the FIB table maintain its table entries in sorted order to ensure the longest prefix match is always returned.
A ternary content addressable memory approach to solving the longest prefix match problem has been previously described. One recent approach is described in Nataraj et al. U.S. Pat. No. 6,499,081 (“Nataraj”), where an attempt has been made to eliminate the prefix ordering and also to decrease the device power consumption at the expense of more complex logic circuits related to prioritizing matched results and extracting the longest prefix match. However, the circuit based approach of a TCAM device remains a major challenge in actual silicon implementation with respect to both power consumption and density, especially if a large number of wide table entries need to be supported. Further, since TCAM devices require multiple transistors to store one bit of information, real estate on a TCAM device is limited. Due to the real estate limitation and the fact that TCAM automatically compares stored entries with incoming keys, typical TCAM devices only store prefix keys, and any data related to a stored key is then typically stored on an external, non-TCAM memory, requiring multiple levels of indirection to access such related data.
There exists a need for an improved solution to the FIB table lookup problem which is algorithmic and may suitably employ less expensive, embedded, dynamic random access memory (DRAM) devices readily available in multiple silicon manufacturing processes.
The present invention addresses the ever expanding speeds and capacity requirements of today's Internet packet routers by providing an advantageous approach that efficiently utilizes embedded DRAM devices as its underlying technology for the search engine, thus reducing power consumption along with increased memory density and resulting in reduced costs when compared to TCAM approaches.